/**
 * @author ChaP
 * @date 2019/04/13
 * @describe:
 */
package CodingTest.AC20190412;

import java.util.*;

public class topkFrequent {
    public List<Integer> topkFrequent(int[] nums, int k){
       Map<Integer,Integer> hs  = new HashMap<>();
       for(int i =0;i<nums.length;i++){
           if(hs.containsKey(nums[i])){
               hs.put(nums[i],hs.get(nums[i])+1);
           }else{
               hs.put(nums[i],1);
           }
       }
        //因为compareTo方法代表的是指定数如果大于参数的话那么则返回1，
        // 实现了comparator中重写compare方法，如果返回值是正数的话，那么就让第二个参数在前面，
        // 如果是负数的话，就让第一个数在前面。
       PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
           @Override
           public int compare(Integer o1, Integer o2) {
               return hs.get(o1) - hs.get(o2);
           }
       });
       for(Integer key:hs.keySet()){
           if(pq.size() < k){
               pq.add(key);
           }else if(hs.get(key) > hs.get(pq.peek())){
               pq.remove();
               pq.add(key);
           }
       }
       List<Integer> res = new ArrayList<>();
       while(!pq.isEmpty()){
           res.add(pq.remove());
       }
       return res;

    }
}
